package cn.initcap.algorithm.graph.util;

import cn.initcap.algorithm.graph.Graph;
import cn.initcap.algorithm.graph.SparseGraph;

/**
 * 判断是否为二分图
 *
 * @author initcap
 * @date Created in 7/30/19 3:05 PM.
 */
public class BipartitionDetection {

    private Graph<Integer, Double> graph;

    private boolean[] visited;

    private int[] colors;

    private boolean isBipartite = true;

    public BipartitionDetection(Graph graph) {
        this.graph = graph;
        visited = new boolean[graph.nodeSize()];
        colors = new int[graph.nodeSize()];

        // 这里将颜色标志为-1，即没有颜色过，当染色时只需要将值设置为0或者1代表两种不同的颜色
        for (int i = 0; i < graph.nodeSize(); i++) {
            colors[i] = -1;
        }

        //这里需要对联通分量进行检测，只要有一个联通分量不是二分图，整张图就不是二分图；
        for (int i = 0; i < graph.nodeSize(); i++) {
            if (!visited[i]) {
                if (!dfs(i, 0)) {
                    isBipartite = false;
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        Graph g = new SparseGraph("algorithm/testG10.txt", false);
        BipartitionDetection bipartitionDetection = new BipartitionDetection(g);
        System.out.println(bipartitionDetection.isBipartite());
    }

    /**
     * 深度优先遍历
     *
     * @param v     顶点
     * @param color v这个顶点会被染成color这个颜色
     * @return true为二分图，false为不是二分图
     */
    private boolean dfs(int v, int color) {
        visited[v] = true;
        colors[v] = color;
        for (int w : graph.adj(v)) {
            if (!visited[w]) {
                if (!dfs(w, 1 - color)) {
                    return false;
                }
            } else if (colors[v] == colors[w]) {
                return false;
            }
        }
        return true;
    }

    public boolean isBipartite() {
        return isBipartite;
    }

}
